/*
 * Maximum Path Sum II Solution.
 */

import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Scanner;

/**
 * Implements a solution to the <a href="http://projecteuler.net/problem=67">
 * Maximum Path Sum II</a> problem on <a href="http://projecteuler.net/">
 * ProjectEuler.net</a>.
 * 
 * This approach uses dynamic programming to directly address the specific 
 * problem.
 * 
 * 
 * @author Michael Silva
 */

public class Euler67DP
{
    
	/**
     * Solves <a href="http://projecteuler.net/problem=67"> Maximum Path Sum II
     * </a> using dynamic programming.
     *
     * @param fname Filename containing the number triangle
     * @return The largest possible sum
     */
    public static int solve (String fname)
    {
        // Count how many lines are in the input file.
        // This causes noticeably slower performance than hard-coding the 
        // array size, but it provides greater flexibility by allowing the 
        // method to handle files of any size.
        int len = countLines(fname);
        
        // Fill in the table using numbers from the input file
        int [][] table = new int [len][len];
        int depth = 0;
        Scanner scanf = getScanner(fname);
        while (scanf.hasNext()){
            
            // Place a row of numbers into the table
            String [] nums = scanf.nextLine().split(" ");
            for (int i=0; i < nums.length; i++){
                table[depth][i] = Integer.parseInt(nums[i]);
            }
            depth++;
        }
        // Close the file
        scanf.close();
        
		// Print the solution
		System.out.println("\n\n\n");
		print(table);
		System.out.println("\n\n\n");
		

        // Use dynamic programming to find the solution
        depth-=2;
        for ( ; depth >= 0; depth--){
            for (int i=0; i <= depth; i++){
                int sum = table[depth][i];
                table[depth][i] = Math.max(sum + table[depth+1][i],
                                            sum + table[depth+1][i+1]);
            }
        }
        
		// Print the solution
		System.out.println("\n\n\n");
		print(table);
		System.out.println("\n\n\n");
		
        // Return the largest sum
        return table[0][0];
    }
    
    
    /**
     * Creates a <code>Scanner</code> object for processing the specified
     * input file.
     * 
     * @param fname Path of the input file.
     * @return <code>Scanner</code> object if successfully opened the input
     * file.
     */
    private static Scanner getScanner(String fname)
    {
        Scanner scanf = null;
        try {
            scanf = new Scanner(
                                new BufferedReader( 
                                    new FileReader(fname)
                                    )
                                );
        } catch (IOException e) { /*Crash!*/ }
        
        return scanf;
    }
    
    
    /**
     * Counts how many lines are in the input file.  This can be used to
     * determine the length and width of the square dynamic programming table.
     * 
     * @param table 
     */
    private static int countLines(String fname)
    {
        // Open the input file
        Scanner scanf = getScanner(fname);
        
        // Count the lines
        int count = 0;
        while (scanf.hasNextLine()){
            count++;
            scanf.nextLine();
        }
        scanf.close();
        
        return count;
    }
    
    
    /**
     * Prints the dynamic programming table.  Useful during testing but only
     * with small tables.
     * 
     * @param table The DP table to be printed.
     */
    private static void print(int [][] table)
    {
        // The length and width of the array.
        // This value can be used because the class uses a square table.
        int len = table[0].length;
        
        for (int i=0; i<len; i++){
            for (int j=0; j<len; j++){
                System.out.print(table[i][j] + " ");
            }
            System.out.println("");
        }
    }
}
